package ca.etsmtl.log320.tp1;

import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

/**
 * 
 * @author Gabriel
 * 
 * Represents a node in a binary tree. Contains a character the the number of times
 * it appears in a specific file.
 *
 */
public class Node implements Comparable<Node>
{
	private Node right;
	private Node left;
	
	/*
	 * The character represented by this node.
	 * If it's Character.UNASSIGNED, it means this node is not a leaf in the binary tree.
	 */
	private char character;
	/*
	 * The number of time the character appears in the original file
	 */
	private int nbOccurrences;
	
	/*
	 * A map containing the associated binary representations of a particular character.
	 * This is obtained by traversing the completed binary tree and the structure is
	 * serialized in the compressed file (acting as a "header").
	 */
	private static Map<Character, String> charCodes = new HashMap<Character, String>();
	
	public Node(char character)
	{
		this.character = character;
		this.nbOccurrences = 1;
	}
	
	public Node(char character, int nbOccurences)
	{
		this.character = character;
		this.nbOccurrences = nbOccurences;
	}
	
	public Node(int nbOccurences)
	{
		this.character = Character.UNASSIGNED;
		this.nbOccurrences = nbOccurences;
	}
		
	/*
	 * Creates a frequency table from a text file.
	 * Frequency tables are used to build the binary tree.
	 */
	private static List<Node> makeFrequencyTable(String path)
	{
		List<Node> frequencyTable = new ArrayList<Node>();
		Map<Character, Integer> frequencyMap = new HashMap<Character, Integer>();
		char c = 0;
		FileReader is;
		
		/*
		 * We're making a Frequency "Map" first instead of a Frequency "List".
		 * A Frequency map is much easier to access and modify than a list of
		 * Nodes.
		 * 
		 * The Node list is generated from the map for convenience.
		 */
		try
		{
			is = new FileReader(path);
		 
			/* Read the file one character at the time until de EOF */
			while((c = (char)is.read()) != (char) -1)
			{
				if(frequencyMap.containsKey(c))
				{
					frequencyMap.put(c, frequencyMap.get(c) + 1);
				}
				else
				{
					frequencyMap.put(c, 1);
				}
			}
			
			is.close();
		}
		catch (FileNotFoundException e)
		{
			e.printStackTrace();
		}
		catch (IOException e)
		{
			e.printStackTrace();
		}
		
		/*
		 * Create the frequency list (aka Node List or frequency table) here
		 */
		Iterator<Map.Entry<Character, Integer>> entries = frequencyMap.entrySet().iterator();
		while (entries.hasNext()) 
		{
		    Map.Entry<Character, Integer> entry = entries.next();
		    frequencyTable.add(new Node(entry.getKey(), entry.getValue()));
		}
		
		return frequencyTable;
	}
	
	/*
	 * Creates a binary tree from a frequency table
	 */
	private static Node createBinaryTree(List<Node> frequencyTable)
	{
		/*
		 * We reduce the table systematically until we get 1 node (the root node)
		 */
		while(frequencyTable.size() != 1)
		{
			Node min1 = frequencyTable.remove(frequencyTable.indexOf(Collections.min(frequencyTable)));
			Node min2 = frequencyTable.remove(frequencyTable.indexOf(Collections.min(frequencyTable)));	
			
			frequencyTable.add(combine(min1, min2));
		}
		
		return frequencyTable.get(0);
	}
	
	/*
	 * Creates a "branch" node (where the character is UNASSIGNED) with 2 leaves 
	 */
	private static Node combine(Node min1, Node min2)
	{
		Node node = new Node(min1.getNbOccurrence() + min2.getNbOccurrence());
		
		node.left = min1;
		node.right = min2;
		
		return node;
	}
	
	/*
	 * Generates a map containing the associated binary representations of a particular character
	 * after traversing the binary tree.
	 */
	private static Map<Character, String> generateCharCodes(Node tree, String code)
	{
		if(tree.getCharacter() != Character.UNASSIGNED)
		{
			charCodes.put(tree.getCharacter(), code);
		}
		
		if(tree.left != null)
		{
			generateCharCodes(tree.left, code + "0");
		}
		
		if(tree.right != null)
		{
			generateCharCodes(tree.right, code + "1");
		}
		
		return charCodes;
	}
	
	/*
	 * Takes the input file and compresses it in the output file
	 */
	public static void compress(String input, String output)
	{
		ObjectOutputStream os;
		FileReader is;
		char c = 0;
		String binaryString = "";
		
		/* Generate frequency table, binary tree, etc. That kind of stuff. */
		generateCharCodes(createBinaryTree(makeFrequencyTable(input)), "");
				
		try
		{
			os = new ObjectOutputStream(new FileOutputStream(output));
			is = new FileReader (input);
			
			os.writeObject(charCodes);
			os.flush();
			
			/* Replace each character in the input file with its corresponding bit sequence */
			while((c = (char)is.read()) != (char) -1)
			{
				binaryString += charCodes.get(c);
				
				/* 
				 * We have to group the bits in bytes to get the best compression.
				 * Once we have a total of bits that can be divided by 1 byte, we can
				 * parse them as bytes and write them to the output file.
				 */
				if(binaryString.length() % 8 == 0)
				{
					String[] byteString = binaryString.split("(?<=\\G.{8})");
					
					for(int i = 0; i < byteString.length; i++)
					{
						/* Parse as Int here because Java is dumb and doesn't have unsigned bytes */
						os.write(Integer.parseInt(byteString[i], 2));
					}

					binaryString = "";
				}
			}
			
			/* We have to write the leftovers to the file, too! */
			if(!binaryString.equals(""))
			{
				/* We need to pad the last byte with zeroes so we can have a complete byte. */
				while(binaryString.length() % 8 != 0)
				{
					binaryString += "0";
				}
				
				String[] byteString = binaryString.split("(?<=\\G.{8})");
				
				for(int i = 0; i < byteString.length; i++)
				{
					os.write(Integer.parseInt(byteString[i], 2));
				}
			}
			
			os.close();
			is.close();
		}
		catch (FileNotFoundException e)
		{
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		catch (IOException e)
		{
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	/*
	 * Takes the input file and decompresses it in the output file.
	 */
	public static void decompress(String input, String output) throws IOException
	{
		ObjectInputStream is = new ObjectInputStream (new FileInputStream(input));
		FileWriter fw = new FileWriter(output);
		BufferedWriter os = new BufferedWriter(fw);
		Object codes = null;
		int b = 0;
		char c = Character.UNASSIGNED;
		String bits = "";
		Map<String, Character> bitCodes = null;
		
		/* 
		 * We need our char codes map first. Since it's our "header", it's the first thing we'll get
		 * from the stream.
		 */
		try
		{
			codes = is.readObject();
		}
		catch (ClassNotFoundException e)
		{
			e.printStackTrace();
		}

		if (codes instanceof Map<?, ?>)
		{
			charCodes = (Map<Character, String>) codes;
			/* 
			 * This is necessary since we also want to get a character 
			 * by it's binary representation.
			 * A bidirectional map might have been useful here.
			 */
			bitCodes = reverse(charCodes);
		}

		try
		{
			/* We read the compressed file byte by byte */
			while ((b = is.read()) != -1) 
			{
				for(int i = 7; i >= 0; i--)
				{
					bits += ((b >> i) & 1);
					
					/* 
					 * Trying to guess which character we're decompressing by
					 * reading the file bit by bit and comparing the current value
					 * with the binary representations in the char codes map.
					 */
					if(!bitCodes.containsKey(bits) && c != Character.UNASSIGNED)
					{
						os.write(c);
						os.flush();
						bits = "" + ((b >> i) & 1);
						c = Character.UNASSIGNED;
					}
					else if(bitCodes.containsKey(bits))
					{
						c = bitCodes.get(bits);
					}
				}
			}
		}
		catch(Exception e)
		{
			e.printStackTrace();
		}

	}
	
	/*
	 * Swaps keys and values in a map.
	 * http://stackoverflow.com/questions/4436999/how-to-swap-keys-and-values-in-a-map-elegantly
	 */
	private static <K,V> HashMap<V,K> reverse(Map<K,V> map) 
	{
	    HashMap<V,K> rev = new HashMap<V, K>();
	    
	    for(Map.Entry<K,V> entry : map.entrySet())
	    {
	        rev.put(entry.getValue(), entry.getKey());
	    }
	    
	    return rev;
	}
	
	public void addOccurrence()
	{
		this.nbOccurrences++;
	}
	
	public int getNbOccurrence()
	{
		return this.nbOccurrences;
	}
	
	public char getCharacter()
	{
		return this.character;
	}
	
	@Override
	public String toString()
	{
		return String.format("%c (%d)", character, nbOccurrences);
	}

	@Override
	public int compareTo(Node n) 
	{
		return (this.getNbOccurrence() > n.getNbOccurrence()) ? 1 : ((this.getNbOccurrence() < n.getNbOccurrence()) ? -1 : 0);
	}
}
